#include "headfiles.h"

using namespace std;

static int subArraySum(int *a, int start, int end) {
    int sum = 0;
    for (int i = start; i <= end; i++) {
        sum += a[i];
    }

    return sum;
}

int minPartition(int *a, int n, int k) {
    if (k == 1) {
        return subArraySum(a, 0, n - 1);
    }

    if (n == 1) {
        return a[0];
    }

    int min_val = 0x7FFFFFFF;
    int i, tmp_min_val, tmp_sum;

    for (i = 1; i < n; i++) {
        tmp_min_val = minPartition(a, i, k - 1);
        tmp_sum = subArraySum(a, i, n - 1);
        tmp_min_val = (tmp_min_val > tmp_sum) ? tmp_min_val : tmp_sum;

        if (min_val > tmp_min_val) {
            min_val = tmp_min_val;
        }
    }

    return min_val;
}

int partitionDP(int *a, int n, int k) {
    if (a == NULL ||
        n <= 0 ||
        k <= 0) {
        cout << "Invalid input array!" << endl;
        return -1;
    }

    if (n == 1) {
        return a[0];
    }

    if (k == 1) {
        return subArraySum(a, 0, n - 1);
    }

    int *matrix = (int *)malloc(sizeof(int) * (n + 1) * (k + 1));
    if (matrix == NULL) {
        cout << "Allocate matrix error!" << endl;
        return -1;
    }
    memset(matrix, 0, sizeof(int) * (n + 1) * (k + 1));


    int *subSum = (int *)malloc(sizeof(int) * (n + 1));
    if (subSum == NULL) {
        cout << "Allocate subsum array error!" << endl;
        return -1;
    }
    memset(subSum, 0, sizeof(int) * (n + 1));

    int i, j, p, loc, min_val;
    for (j = 1; j <= n; j++) {
        subSum[j] = subSum[j - 1] + a[j - 1];
        loc = j * (k + 1) + 1;
        matrix[loc] = subSum[j];
    }

    for (i = 1; i <= k; i++) {
        loc = k + 1 + i;
        matrix[loc] = a[0];
    }

    for (i = 2; i <= k; i++) {
        for (j = 2; j <= n; j++) {
            min_val = 0x7FFFFFFF;
            for (p = 1; p <= j; p++) {
                int tmp1 = matrix[p * (k + 1) + i - 1];
                int tmp2 = subSum[j] - subSum[p];
                int tmp = tmp1 > tmp2 ? tmp1 : tmp2;
                if (tmp < min_val) {
                    min_val = tmp;
                }
            }
            loc = j * (k + 1) + i;
            matrix[loc] = min_val;
        }
    }

    loc = n * (k + 1) + k;
    min_val = matrix[loc];

    free(matrix);
    free(subSum);

    return min_val;
}

static int getMinCost(int *a, int n) {
    int min_cost = 0;
    int i;
    for (i = 0; i < n; i++) {
        if (min_cost < a[i]) {
            min_cost = a[i];
        }
    }

    return min_cost;
}

static int getMaxCost(int *a, int n) {
    int max_cost = 0;
    int i;
    for (i = 0; i < n; i++) {
        max_cost += a[i];
    }

    return max_cost;
}

static int calcRequiredPainters(int *a, int n, int cost) {
    int painter_num = 0;
    int painter_cost = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > cost) {
            cout << "Error input!" << endl;
            return -1;
        }

        if (painter_cost + a[i] > cost) {
            painter_num++;
            painter_cost = 0;
        }
        painter_cost += a[i];
    }

    return painter_num + 1;
}

int partitionBinarySearch(int *a, int n, int k) {
    int min_cost = getMinCost(a, n);
    int max_cost = getMaxCost(a, n);

    while (min_cost < max_cost) {
        int cost = (min_cost + max_cost) / 2;
        int required_painter_num = calcRequiredPainters(a, n, cost);
        if (required_painter_num > k) {
            min_cost = cost + 1;
        }
        else {
            max_cost = cost;
        }
    }

    return min_cost;
}




